package leetcode.code1334;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int findTheCity(int n, int[][] edges, int distanceThreshold) {
		int[][] weight = new int[n][n];
		List<Integer>[] indexs = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			indexs[i] = new ArrayList<>();
		}
		int[] mins = new int[n];
		Arrays.fill(mins, Integer.MAX_VALUE);
		for (int i = 0; i < edges.length; i++) {
			int[] e = edges[i];
			int f = e[0], t = e[1], w = e[2];
			mins[f] = Math.min(mins[f], w);
			mins[t] = Math.min(mins[t], w);
			weight[f][t] = w;
			weight[t][f] = w;
			indexs[f].add(t);
			indexs[t].add(f);
		}
		int ans = 0, num = n;
		for (int i = 0; i < n; i++) {
			if (mins[i] > distanceThreshold) {
				ans = i;
				num = 0;
				continue;
			}
			if (num == 0) {
				continue;
			}
			Queue<int[]> queue = new LinkedList<>();
			Integer[] been = new Integer[n];
			been[i] = distanceThreshold;
			queue.add(new int[] { i, distanceThreshold });
			int cnt = 0;
			while (!queue.isEmpty()) {
				int[] cur = queue.poll();
				int f = cur[0], rest = cur[1];
				List<Integer> next = indexs[f];
				for (int t : next) {
					if (weight[f][t] <= rest && (been[t] == null || rest - weight[f][t] > been[t])) {
						if (been[t] == null) {
							cnt++;
						}
						been[t] = rest - weight[f][t];
						queue.add(new int[] { t, rest - weight[f][t] });
					}
				}
			}
			if (cnt < num) {
				num = cnt;
				ans = i;
			} else if (cnt == num) {
				ans = i;
			}
		}
		return ans;
	}

	private void tu(int n, int[][] edges) {
		int[][] weight = new int[n][n];// 权重表
		List<Integer>[] indexs = new ArrayList[n];// 邻接表
		for (int i = 0; i < n; i++) {
			indexs[i] = new ArrayList<>();
		}
		int[] mins = new int[n];// 最小权值
		Arrays.fill(mins, Integer.MAX_VALUE);
		for (int i = 0; i < edges.length; i++) {
			int[] e = edges[i];
			int f = e[0], t = e[1], w = e[2];
			mins[f] = Math.min(mins[f], w);
			mins[t] = Math.min(mins[t], w);
			weight[f][t] = w;
			weight[t][f] = w;
			indexs[f].add(t);
			indexs[t].add(f);
		}
	}

	@Override
	public void debug4() {
		H.compare(3, this.findTheCity(4, H.str2array1("[[0,1,3],[1,2,1],[1,3,4],[2,3,1]]"), 4));
		H.compare(5, this.findTheCity(6, H.str2array1("[[0,1,10],[0,2,1],[2,3,1],[1,3,1],[1,4,1],[4,5,10]]"), 20));
		H.compare(0, this.findTheCity(5, H.str2array1("[[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]]"), 2));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
